In mathematics, a shuffle algebra is a
Hopf algebra Hopf is a German surname. Notable people with the surname include:
*Eberhard Hopf (1902–1983), Austrian mathematician
*Hans Hopf (1916–1993), German tenor
*Heinz Hopf (1894–1971), German mathematician
*Heinz Hopf (actor) (1934–2001), Swedis ...
with a basis corresponding to words on some set, whose product is given by the shuffle product ''X'' ⧢ ''Y'' of two words ''X'', ''Y'': the sum of all ways of interlacing them. The interlacing is given by the
riffle shuffle permutation In the mathematics of permutations and the study of shuffling playing cards, a riffle shuffle permutation is one of the permutations of a set of n items that can be obtained by a single riffle shuffle, in which a sorted deck of n cards is cut into t ...
.
The shuffle algebra on a finite set is the graded dual of the
universal enveloping algebra
In mathematics, the universal enveloping algebra of a Lie algebra is the unital associative algebra whose representations correspond precisely to the representations of that Lie algebra.
Universal enveloping algebras are used in the representati ...
of the
free Lie algebra In mathematics, a free Lie algebra over a field ''K'' is a Lie algebra generated by a set ''X'', without any imposed relations other than the defining relations of alternating ''K''-bilinearity and the Jacobi identity.
Definition
The definition ...
on the set.
Over the rational numbers, the shuffle algebra is isomorphic to the
polynomial algebra
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables) ...
in the
Lyndon word
In mathematics, in the areas of combinatorics and computer science, a Lyndon word is a nonempty string that is strictly smaller in lexicographic order than all of its rotations. Lyndon words are named after mathematician Roger Lyndon, who investi ...
s.
The shuffle product occurs in generic settings in
non-commutative algebra
In mathematics, a noncommutative ring is a ring whose multiplication is not commutative; that is, there exist ''a'' and ''b'' in the ring such that ''ab'' and ''ba'' are different. Equivalently, a ''noncommutative ring'' is a ring that is not a ...
s; this is because it is able to preserve the relative order of factors being multiplied together - the
riffle shuffle permutation In the mathematics of permutations and the study of shuffling playing cards, a riffle shuffle permutation is one of the permutations of a set of n items that can be obtained by a single riffle shuffle, in which a sorted deck of n cards is cut into t ...
. This can be held in contrast to the
divided power structure
In mathematics, specifically commutative algebra, a divided power structure is a way of making expressions of the form x^n / n! meaningful even when it is not possible to actually divide by n!.
Definition
Let ''A'' be a commutative ring with an ...
, which becomes appropriate when factors are commutative.
Shuffle product
The shuffle product of words of lengths ''m'' and ''n'' is a sum over the ways of interleaving the two words, as shown in the following examples:
:''ab'' ⧢ ''xy'' = ''abxy'' + ''axby'' + ''xaby'' + ''axyb'' + ''xayb'' + ''xyab''
:''aaa'' ⧢ ''aa'' = 10''aaaaa''
It may be defined inductively by
:''u'' ⧢ ε = ε ⧢ ''u'' = ''u''
:''ua'' ⧢ ''vb'' = (''u'' ⧢ ''vb'')''a'' + (''ua'' ⧢ ''v'')''b''
where ε is the
empty word
In formal language theory, the empty string, or empty word, is the unique string of length zero.
Formal theory
Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special cas ...
, ''a'' and ''b'' are single elements, and ''u'' and ''v'' are arbitrary words.
The shuffle product was introduced by . The name "shuffle product" refers to the fact that the product can be thought of as a sum over all ways of
riffle shuffling two words together: this is the
riffle shuffle permutation In the mathematics of permutations and the study of shuffling playing cards, a riffle shuffle permutation is one of the permutations of a set of n items that can be obtained by a single riffle shuffle, in which a sorted deck of n cards is cut into t ...
. The product is
commutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name o ...
and
associative
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
.
The shuffle product of two words in some alphabet is often denoted by the shuffle product symbol ⧢ (
Unicode
Unicode, formally The Unicode Standard,The formal version reference is is an information technology Technical standard, standard for the consistent character encoding, encoding, representation, and handling of Character (computing), text expre ...
character U+29E2 , derived from the
Cyrillic
, bg, кирилица , mk, кирилица , russian: кириллица , sr, ћирилица, uk, кирилиця
, fam1 = Egyptian hieroglyphs
, fam2 = Proto-Sinaitic
, fam3 = Phoenician
, fam4 = G ...
letter
sha).
Infiltration product
The closely related infiltration product was introduced by . It is defined inductively on words over an alphabet ''A'' by
:''fa'' ↑ ''ga'' = (''f'' ↑ ''ga'')''a'' + (''fa'' ↑ ''g'')''a'' + (''f'' ↑ ''g'')''a''
:''fa'' ↑ ''gb'' = (''f'' ↑ ''gb'')''a'' + (''fa'' ↑ ''g'')''b''
For example:
:''ab'' ↑ ''ab'' = ''ab'' + 2''aab'' + 2''abb'' + 4 ''aabb'' + 2''abab''
:''ab'' ↑ ''ba'' = ''aba'' + ''bab'' + ''abab'' + 2''abba'' + 2''baab'' + ''baba''
The infiltration product is also commutative and associative.
See also
*
Hopf algebra of permutations In algebra, the Malvenuto–Poirier–Reutenauer Hopf algebra of permutations or MPR Hopf algebra is a Hopf algebra with a basis of all elements of all the finite symmetric groups ''S'n'', and is a non-commutative analogue of the Hopf algebra of ...
*
Zinbiel algebra In mathematics, a Zinbiel algebra or dual Leibniz algebra is a module over a commutative ring with a bilinear product satisfying the defining identity:
:(a \circ b) \circ c = a \circ (b \circ c) + a \circ (c \circ b).
Zinbiel algebras were introd ...
References
*
*
*
*
*
*
*
{{refend
External links
Shuffle product symbol
Combinatorics
Algebra